1. Field of the Invention
The present invention relates to a digital operation unit, and particularly relates to a redundant binary type digital operation unit which processes operation using redundant binary notation.
2. Description of the Prior Art
Conventionally, a redundant binary type digital operation unit of this kind have judged whether an operation data is overflowing or not by either of the following two methods. The first one detects an overflow by, after converting the operation data into binary numbers, giving the sign contrary to that of the redundant binary data to the binary data. The second one judges the data overflowing when a carry from the redundant binary operation circuit occurs, reasoning from degraded integrity of redundant binary data.
The redundant binary number here means a method of is expressed by three values "1", "0", and "-1". This can eliminate the propagation of carries in operation, which results in a fixed operation time regardless of the operation word length. The three values of a redundant binary number are respectively given in two bits: 01 (=1), 00 (=0), and 11 (=-1). Since each digit may be "1", "0" or "-1" ("-1" is hereinafter referred to as "T" for convenience), the maximum value of an eight-digit number, for example, is "11111111" (=255), and the minimum value in this case is "TTTTTTTT" (=-255). This way of expression can cover a wider data range with the same word length than ordinary binary notation. In particular, fixed operation speed regardless of operation word length enables a high-speed operation circuit for operations where data are accumulated such as filter operation. Specifically, time-consuming process of conversion from redundant binary numbers to binary numbers is arranged like pipelines so that the redundant binary data are accumulated at a high speed and then the results are converted from a redundant binary number to a binary number.
The redundant binary operation method is to prevent a carry from being propagated. With this method, when summing two data, the values at the digits immediately below the one to be calculated are first referred to so as to generate an intermediate carry and sum, which are used for processing a carry from the lower digit.
For example, if the digit n ("n"th digit) of the augend data is "1" and the digit n of the addend data is "0", a carry from a lower digit causes further carries to the digits higher than the digit n, resulting in carry propagation. To avoid this, the status at the digit immediately below the digit n is checked first and, if there's a possibility of a carry, a carry of "1" is given to the digit n+1 in advance with keeping an intermediate sum of "T". This can stop the propagation of a carry by operation "1+T=0" even if a carry occurs from the lower digit. Table 1 shows the operation rule in the first step of the redundant binary addition. In this table, the augend at digit n is expressed as Xn, the addend at digit n is Yn, the values at the digits immediately below digit n for augend and addend Xn-1 and Yn-1 respectively, the carry Ci and the intermediate sum Si.
TABLE 1 ______________________________________ (XN) (YN) (Xn-1, Yn-1) (Ci) (Si) ______________________________________ 1 1 1 0 1 0 Both are positive 1 T 0 1 Either is negative at least 0 1 0 0 1 T 0 0 T 1 0 T Both are positive 0 T T 0 Either is negative at least T 1 T T T 0 ______________________________________
Suppose a binary number expressed as an eight-bit data "01100000" (=96) now. Since a binary number can be converted into a redundant binary number just by reversing the sign at the sign bit, the above value is "01100000" in redundant binary notation, too. If "0" is added according to the rule shown in Table 1, the operation result will be: ##STR1## where (1) means an overflow.
Thus, even a value which can be expressed in binary notation can, if expressed in redundant binary notation, can cause an overflow when "0" is added to the value, and the data cannot be held.
Such a conventional redundant binary operation circuit always detects an overflow by converting the operation data into binary numbers. For example, accumulation can be processed at a higher speed by using the redundant binary operation method, but the accumulation results have to be converted into binary numbers for overflow judgment when there's a possibility of overflow. This results in a reduced speed of operation.
Another drawback of the conventional method is that a carry signal can be generated even when overflow does not occur actually, since the values of redundant binary notation are expressed with three values "1", "0" and "-1", and the same value can be expressed in various ways. For example, the value "5" in decimal notation is "0101" in binary notation, and in redundant binary notation, this value may be a four-digit number "lTlT" or five-digit number "lTOTT". When the decimal number "5" is expressed in the redundant binary notation as a five-digit number "lTOTT", a carry signal occurs if the operation circuit is made for the operation word length of four digits. In this case, the value is judged overflow, though the actual value does not overflow. In addition, a conventional redundant binary operation circuit judges the status of the digit immediately below the one to be processed. This means that, among the values causing a carry signal with operation output, negative values have larger absolute values than positive ones, resulting in deviation between positive and negative values. Specifically, when supposing two values "+8" and "-8" expressed in four digits, "+8" is expressed as "1000" in redundant binary notation and "-8" as "TOOO". For example, if O is added to both numbers, an overflow occurs only when the number is positive as shown below. ##STR2##